%!TEX root = /Users/adriaan/cw/phd/write-ups/sparsec/sparsec.tex
\chapter{Solutions to Selected Exercises}

\begin{sol}[Of exercise \ref{ex:equivalence}] \label{sol:equivalence} Listing \ref{lst:equivalence} details the steps to relate the two implementations of \lstinline!~!.
\end{sol}

\begin{lstlisting}[caption=Expansion,label=lst:equivalence]
// given:
def flatMap[U](f: T => Parser[U]): Parser[U] 
  = new Parser[U]{def apply(in: Input) = Parser.this(in) flatMapWithNext(f)}

def map[U](f: T => U): Parser[U] 
  = new Parser[U]{def apply(in: Input) = Parser.this(in) map(f)}
  
def flatMapWithNext[U](f: T => Input => Result[U]): Result[U] = this match {
  case Success(x, i) => f(x)(i)
  case Failure(e, n) => Failure(e, n)
}   
def map[U](f: T => U): Result[U] = this match {
  case Success(x, i) => Success(f(x), i)
  case Failure(e, n) => Failure(e, n)
} 

// expansion:
def ~ [U](p: => Parser[U]): Parser[Pair[T, U]] 
= for(a <- this; b <- p) yield (a,b)
= this.flatMap{a => p.map{b => (a, b)}}
= this.flatMap{a => new Parser[Pair[T, U]]{def apply(in: Input) = p(in) map{b => (a, b)}}}
= new Parser{def apply(in: Input) = 
    Parser.this(in) flatMapWithNext{a => 
      new Parser[Pair[T, U]]{def apply(in: Input) = 
        p(in) map{b => (a, b)}
      }
    }
  }
= new Parser{def apply(in: Input) = 
    Parser.this(in) match {
      case Success(x, i) => {a => 
        new Parser[Pair[T, U]]{def apply(in: Input) = 
          p(in) map{b => (a, b)}
        }
      }(x)(i)
      case Failure(e, n) => Failure(e, n)
    }
  } 
= new Parser{def apply(in: Input) = 
    Parser.this(in) match {
      case Success(x, i) => 
        new Parser[Pair[T, U]]{def apply(in: Input) = 
          p(in) map{b => (x, b)}
        }(i)
      case Failure(e, n) => Failure(e, n)
    }
  } 
= new Parser{def apply(in: Input) = 
    Parser.this(in) match {
      case Success(x, i) => p(i) map{b => (x, b)}
      case Failure(e, n) => Failure(e, n)
    }
 } 
= new Parser{def apply(in: Input) = 
    Parser.this(in) match {
      case Success(x, i) => p(i) match {
        case Success(x2, i) => Success({b => (x, b)}(x2), i)
        case Failure(e, n) => Failure(e, n)
      } 
      case Failure(e, n) => Failure(e, n)
    }
  } 
= new Parser[Pair[T, U]]{ def apply(in: Input) = 
    Parser.this(in) match {
      case Success(x, next) => p(next) match {
        case Success(x2, next2) => Success((x, x2), next2)
        case Failure(e, n) => Failure(e, n)
      } 
      case Failure(e, n) => Failure(e, n)
    }
  }  
\end{lstlisting}

\begin{sol}[Of exercise \ref{ex:filter}] \label{sol:filter} Listing \ref{lst:filter} shows the implementation of \code{filter} in \type{Success} (in \type{Failure}, it simply returns \code{this}), as well as the correct version of \code{consumeFirst}.
\end{sol}

A correct implementation of \code{filter} requires each successful result to know what should happen in case it is filtered out: we cannot simply ``invent'' the failure that occurs when \code{filter}'s predicate is not met! Therefore, we add a \code{zero} member to \type{Success}, which determines how \code{filter} on a \type{Success} fails.

This way, \code{consumeFirst} can produce successes that ``un-consume'' their input if they are refuted by \code{filter}. The next parser will then be applied to the input that \code{consumeFirst} would have consumed, had it been successful.

\begin{lstlisting}[caption=Filtering with zero,label=lst:filter]
  case class Success[+T](result: T, next: Input)(val zero: Failure) extends Result[T] {
    def map[U](f: T => U)                              
      = Success(f(result), next)(zero)
    def flatMap[U](f: T => Result[U])                  
      = f(result)   
    def flatMapWithNext[U](f: T => Input => Result[U]) 
      = f(result)(next)    
    def filter(f: T => Boolean): Result[T]             
      = if(f(result)) this else zero
    def append[U >: T](alt: => Result[U])              
      = this
  }

  def consumeFirst: Parser[Elem] = Parser{in => 
    Success(first(in), rest(in))(Failure("unknown failure", in))
  }
\end{lstlisting}

